/**
 * 剑指 Offer 41. 数据流中的中位数
 * https://leetcode-cn.com/problems/shu-ju-liu-zhong-de-zhong-wei-shu-lcof/
 */

/**
 * @param {number} target
 * @param {number[]} nums
 * @return {number}
 */
function find(target, nums) {
  let left = 0;
  let right = nums.length - 1;
  while (left <= right) {
    const middle = Math.floor((left + right) / 2);
    if (nums[middle] === target) {
      return middle;
    }
    if (nums[middle] < target) {
      if (middle >= nums.length - 1 || nums[middle + 1] >= target) {
        return middle + 1;
      }
      left = middle + 1;
    } else {
      right = middle - 1;
    }
  }
  return 0;
}

function MedianFinder() {
  this.nums = [];
  this.median = -1;
}

/**
 * @param {number} num
 * @return {void}
 */
MedianFinder.prototype.addNum = function (num) {
  const { nums } = this;
  const index = find(num, nums);
  nums.splice(index, 0, num);
  const middle = nums.length / 2;
  if (Number.isInteger(middle)) {
    this.median = (nums[middle - 1] + nums[middle]) / 2;
  } else {
    this.median = nums[Math.floor(middle)];
  }
};

/**
 * @return {number}
 */
MedianFinder.prototype.findMedian = function () {
  return this.median;
};

const medianFinder = new MedianFinder();
medianFinder.addNum(1);
medianFinder.addNum(2);
console.log(medianFinder.findMedian() === 1.5);
medianFinder.addNum(3);
console.log(medianFinder.findMedian() === 2);
